package homework;

import java.util.Random;

/**
 * @author noob
 * @version 1.0
 * @date 2021/3/17 7:11
 */
public class SelectK {


    public  int selectk(int[] arr,int left,int right,int k){
        int p =partitiion(arr,left,right);

        if(k==p){
            return  arr[p];
        }
        if(k<p){
            return selectk(arr,left,p-1,k);
        }else{
            return selectk(arr,p+1,right,k);
        }

    }







    private  int partitiion(int[] arr, int left, int right){

        int index = (new Random()).nextInt(right-left+1)+left;
        exchange(arr,left,index);




        int i = left + 1;
        int j = right;
        while (true){

            while (i<=j && arr[i] < arr[left]){
                i++;
            }
            while ( j >= i && arr[j] > arr[left]){
                j--;
            }
//            情况1：退出循环
            if( j <= i ) {
                break;
            }


//            情况2：就交换
            exchange(arr,i,j);
            i++;
            j--;
        }

        exchange(arr,left,j);
        return j;

    }

    private  void exchange(int[] arr, int i, int j) {
        int t = arr[i];
        arr[i] =arr[j];
        arr[j] = t;
    }


}
